#include <stdio.h>
#define MAXLEN 255

typedef struct String
{
    char ch[MAXLEN];
    int Length;
} SString;

bool StrAssign(SString &T, char c);                        // 赋值
bool StrCopy(SString &T, SString S);                       // 复制
bool StrEmpty(SString T);                                  // 判空
int StrCompare(SString S, SString T);                      // 比较
int StrLength(SString S);                                  // 长度
bool ClearString(SString &S);                              // 清空
bool Concat(SString &T, SString S1, SString S2);           // 拼接
bool SubString(SString &Sub, SString S, int pos, int len); // 截取
int Index(SString S, SString T, int pos);                  // 查找
bool Replace(SString &S, SString T, SString V);            // 替换
bool StrInsert(SString &S, int pos, SString T);            // 插入
bool StrDelete(SString &S, int pos, int len);              // 删除
bool Destroy(SString &S);                                  // 销毁

void StrInit(SString &T)
{
    for (int i = 0; i < MAXLEN; i++)
    {
        T.ch[i] = ' ';
    }
    T.Length = 0;
}

bool StrAssign(SString &T, char c)
{
    T.ch[++T.Length] = c;
    return true;
}

// 长度
int StrLength(SString S)
{
    return S.Length;
}

// 比较
int StrCompare(SString S, SString T)
{
    for (int i = 1; i < S.Length && i < T.Length; i++)
    {
        if (S.ch[i] != T.ch[i])
            return S.ch[i] - T.ch[i];
    }
    return S.Length - T.Length;
}

// 截取
bool SubString(SString &Sub, SString S, int pos, int len)
{
    if (pos + len - 1 > S.Length)
        return false;
    for (int i = pos; i < pos + len; i++)
        Sub.ch[i - pos + 1] = S.ch[i];
    Sub.Length = len;
    return true;
}

// 定位
int Index(SString S, SString T, int pos)
{
    int i = 1, n = StrLength(S), m = StrLength(T);
    SString Sub;
    while (i <= n - m + 1)
    {
        SubString(Sub, S, i, m);
        if (StrCompare(Sub, T))
            i++;
        else
            return i;
    }
    return 0;
}

// 朴素匹配算法
int SimplicityIndex(SString S, SString T)
{
    int i = 1, j = 1, k = 1;
    while (i <= S.Length && T.Length)
    {
        if (S.ch[i] == T.ch[i])
        {
            ++i;
            ++j;
        }
        else
        {
            k++;
            i = k;
            j = 1;
        }
    }
    if (j > T.Length)
        return k;
    else
        return 0;
}

// KMP算法
void get_next(SString T, int next[])
{
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.Length)
    {
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

int KMPIndex(SString S, SString T)
{
    int i = 1, j = 1;
    int next[T.Length + 1];
    get_next(T, next);
    while (i <= S.Length && j <= T.Length)
    {
        if (j == 0 || S.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
        }
        else
            j = next[j];
    }
    if (j > T.Length)
        return i - T.Length;
    else
        return 0;
}

void Print(SString S)
{
    for (int i = 1; i < S.Length + 1; i++)
    {
        printf("%c", S.ch[i]);
    }
    printf("\n");
}

int main()
{
    SString S, T;
    StrInit(S);
    StrInit(T);
    StrAssign(S, 'g');
    StrAssign(S, 'o');
    StrAssign(S, 'o');
    StrAssign(S, 'g');
    StrAssign(S, 'l');
    StrAssign(S, 'e');

    StrAssign(T, 'g');
    StrAssign(T, 'o');
    StrAssign(T, 'o');

    Print(S);
    Print(T);

    int res = KMPIndex(S, T);
    printf("%d ", res);
}